package sun.superstring;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

// 方式一：从有序的状态出发，通过执行一系列有效的移动（即滑动空格）来生成一个新的布局。
// 这种方法可以确保生成的新布局是可解的，因为它是从一个
// 已知的可解状态（通常是按顺序排列的状态）经过一系列合法操作得到的。
public class PuzzleShuffler {

    private static final Random rand = new Random();

    public static void main(String[] args) {
        int size = 4; // 数字华容道大小，这里是4x4
        int[][] puzzle = generateSolvablePuzzle(size);
        printPuzzle(puzzle);
    }

    /**
     * 生成一个可解的数字华容道布局
     */
    private static int[][] generateSolvablePuzzle(int size) {
        int[][] puzzle = createOrderedPuzzle(size); // 创建一个有序的拼图
        printPuzzle(puzzle);
        shufflePuzzle(puzzle, size * size * 100); // 随机移动空格一定次数
        return puzzle;
    }

    /**
     * 创建一个有序的数字华容道布局
     */
    private static int[][] createOrderedPuzzle(int size) {
        int[][] puzzle = new int[size][size];
        int num = 1;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i == size - 1 && j == size - 1) { // 最后一格留为空白
                    puzzle[i][j] = 0;
                } else {
                    puzzle[i][j] = num++;
                }
            }
        }
        return puzzle;
    }

    /**
     * 打乱拼图，通过随机移动空白块多次
     */
    private static void shufflePuzzle(int[][] puzzle, int shuffleCount) {
        int size = puzzle.length;
        int blankX = size - 1, blankY = size - 1; // 初始时空白块位于右下角

        for (int i = 0; i < shuffleCount; i++) {
            // 获取空白块周围的有效移动位置
            List<int[]> validMoves = getValidMoves(blankX, blankY, size);

            // 随机选择一个有效移动
            int[] move = validMoves.get(rand.nextInt(validMoves.size()));
            int newX = move[0], newY = move[1];

            // 移动空白块
            puzzle[blankX][blankY] = puzzle[newX][newY];
            puzzle[newX][newY] = 0;

            // 更新空白块的位置
            blankX = newX;
            blankY = newY;
        }
    }

    /**
     * 获取空白块周围的合法移动位置
     */
    private static List<int[]> getValidMoves(int x, int y, int size) {
        List<int[]> moves = new ArrayList<>();
        if (x > 0) moves.add(new int[]{x - 1, y}); // 上移
        if (x < size - 1) moves.add(new int[]{x + 1, y}); // 下移
        if (y > 0) moves.add(new int[]{x, y - 1}); // 左移
        if (y < size - 1) moves.add(new int[]{x, y + 1}); // 右移
        return moves;
    }

    /**
     * 打印拼图
     */
    private static void printPuzzle(int[][] puzzle) {
        for (int[] row : puzzle) {
            for (int tile : row) {
                System.out.print((tile == 0 ? "  " : String.format("%2d", tile)) + " ");
            }
            System.out.println();
        }
    }
}